Alien dictionary [Topological Sort, DFS, BFS]¶
Time: O(N); Space: O(V+E); hard
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Note:
You may assume all letters are in lowercase.
The dictionary is invalid, if a is prefix of b and b is appear before a.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return the smallest in normal lexicographical order.
Have you met this question in a real interview?
Example 1:
Input: words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]
Output: “wertf”
Explanation:
from “wrt”and“wrf”, we can get ‘t’<‘f’
from “wrt”and“er”, we can get ‘w’<‘e’
from “er” and“ett”, we can get ‘r’<‘t’
from “ett”and“rftt”,we can get ‘e’<‘r’
So return “wertf”
Example 2:
Input: words = [“z”,“x”]
Output: “zx”
Explanation:
from “z” and “x”?we can get ‘z’ < ‘x’
So return “zx”
[1]:
from collections import deque
class Solution1(object):
'''
BFS solution.
'''
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
result, zero_in_degree_queue, in_degree, out_degree = [], deque(), {}, {}
nodes = set()
for word in words:
for c in word:
nodes.add(c)
for i in range(1, len(words)):
if len(words[i-1]) > len(words[i]) and \
words[i-1][:len(words[i])] == words[i]:
return ""
self.findEdges(words[i - 1], words[i], in_degree, out_degree)
for node in nodes:
if node not in in_degree:
zero_in_degree_queue.append(node)
while zero_in_degree_queue:
precedence = zero_in_degree_queue.popleft()
result.append(precedence)
if precedence in out_degree:
for c in out_degree[precedence]:
in_degree[c].discard(precedence)
if not in_degree[c]:
zero_in_degree_queue.append(c)
del out_degree[precedence]
if out_degree:
return ""
return "".join(result)
# Construct the graph.
def findEdges(self, word1, word2, in_degree, out_degree):
str_len = min(len(word1), len(word2))
for i in range(str_len):
if word1[i] != word2[i]:
if word2[i] not in in_degree:
in_degree[word2[i]] = set()
if word1[i] not in out_degree:
out_degree[word1[i]] = set()
in_degree[word2[i]].add(word1[i])
out_degree[word1[i]].add(word2[i])
break
[2]:
s = Solution1()
words = ["wrt", "wrf", "er", "ett", "rftt"]
assert s.alienOrder(words) == "wertf"
words = ["z","x"]
assert s.alienOrder(words) == "zx"
[3]:
class Solution2(object):
'''
DFS solution.
'''
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
# Find ancestors of each node by DFS.
nodes, ancestors = set(), {}
for i in range(len(words)):
for c in words[i]:
nodes.add(c)
for node in nodes:
ancestors[node] = []
for i in range(1, len(words)):
if len(words[i-1]) > len(words[i]) and \
words[i-1][:len(words[i])] == words[i]:
return ""
self.findEdges(words[i - 1], words[i], ancestors)
# Output topological order by DFS.
result = []
visited = {}
for node in nodes:
if self.topSortDFS(node, node, ancestors, visited, result):
return ""
return "".join(result)
# Construct the graph.
def findEdges(self, word1, word2, ancestors):
min_len = min(len(word1), len(word2))
for i in range(min_len):
if word1[i] != word2[i]:
ancestors[word2[i]].append(word1[i])
break
# Topological sort, return whether there is a cycle.
def topSortDFS(self, root, node, ancestors, visited, result):
if node not in visited:
visited[node] = root
for ancestor in ancestors[node]:
if self.topSortDFS(root, ancestor, ancestors, visited, result):
return True
result.append(node)
elif visited[node] == root:
# Visited from the same root in the DFS path.
# So it is cyclic.
return True
return False
[4]:
s = Solution2()
words = ["wrt", "wrf", "er", "ett", "rftt"]
assert s.alienOrder(words) == "wertf"
words = ["z","x"]
assert s.alienOrder(words) == "zx"